﻿using System;
using Algoritmia.DataStructures.Lists;
using Algoritmia.Utils;

namespace Algoritmia.Problems.SequenceComparison.EditDistance
{
    public class SpaceSavingEditDistanceComputer<T>
    {
        private readonly EqualityComparison<T> _equalityComparison;

        public SpaceSavingEditDistanceComputer(EqualityComparison<T> equalityComparison = null)
        {
            _equalityComparison = AlgoritmiaFactory.GetDefaultEqualityComparison(equalityComparison);
        }

        public int Distance(IList<T> x, IList<T> y)
        {
            var currentRow = new int[x.Count + 1];
            var previousRow = new int[x.Count + 1];
            currentRow[0] = 0;
            for(int i = 1; i <= x.Count; i++)
            {
                currentRow[i] = currentRow[i - 1] + 1;
            }
            for(int j = 1; j <= y.Count; j++)
            {
                var aux = currentRow;
                currentRow = previousRow;
                previousRow = aux;
                currentRow[0] = previousRow[0] + 1;
                for(int i = 1; i <= x.Count; i++)
                {
                    currentRow[i] = Math.Min(currentRow[i - 1] + 1, previousRow[i] + 1);
                    currentRow[i] = Math.Min(currentRow[i],
                                             previousRow[i - 1] + (_equalityComparison(x[i - 1], y[j - 1]) ? 0 : 1));
                }
            }
            return currentRow[x.Count];
        }
    }

    public class SpaceSavingEditDistanceComputer : SpaceSavingEditDistanceComputer<char>
    {
        public int Distance(string x, string y)
        {
            return base.Distance(x.ToAlgoritmiaList(), y.ToAlgoritmiaList());
        }
    }
}
